package leetcode.D100.T16;

import java.util.Arrays;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-25 15:44:14 星期五
 */
class Solution {

    /**
     * 一刷
     * 解法类似于三数量之和，外层for循环，里层双指针，总复杂度为O(n2)
     */
    private int minDist = Integer.MAX_VALUE;
    private int result = 0;

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        for(int i=0; i<nums.length-2; ++i) {
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            twoSumClosest(nums, i+1, target-nums[i]);
            if (minDist == 0)
                break;
        }
        return result;
    }

    private void twoSumClosest(int[] nums, int start, int target) {
        int localMinDist = Integer.MAX_VALUE;
        int left = start, right = nums.length-1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            int dist = sum > target ? sum-target : target-sum;
            if (dist < minDist) {
                minDist = dist;
                result = sum + nums[start-1];
            }
            int leftBase = nums[left], rightBase = nums[right];
            if (sum < target) {
                while (left < right && nums[left] == leftBase)
                    left++;
            } else if (sum > target) {
                while (left < right && nums[right] == rightBase)
                    right--;
            } else {
                minDist = 0;
                result = sum + nums[start-1];
                return;
            }
        }
    }
}